//给定一个非空的字符串
// s ，检查是否可以通过由它的一个子串重复多次构成。
//
//
//
// 示例 1:
//
//
//输入: s = "abab"
//输出: true
//解释: 可由子串 "ab" 重复两次构成。
//
//
// 示例 2:
//
//
//输入: s = "aba"
//输出: false
//
//
// 示例 3:
//
//
//输入: s = "abcabcabcabc"
//输出: true
//解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
//
//
//
//
// 提示：
//
//
//
//
//
// 1 <= s.length <= 10⁴
// s 由小写英文字母组成
//
//
// Related Topics 字符串 字符串匹配 👍 950 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function repeatedSubstringPattern(s: string): boolean {

    /*
    a b c d a b d
    0 0 0 0 1 2 0
    a b a b
    0 0 1 2
    a b c a b c a b c a b c
    0,0,0,1,2,3,4,5,6,7,8,9
     */

    function getNext(str: string): number[] {
        let next: number[] = [];
        let j: number = 0;
        next[0] = j;
        // 求最长相同前后缀长度 弄到next数组里
        for (let i = 1, length = str.length; i < length; i++) {
            // str[i] !== str[j] 即当遇到不匹配的单词时 退回前缀匹配的后一个的下标
            while (j > 0 && str[i] !== str[j]) {
                // 使j跳到前一个最大相同前后缀长度的位置，即跳到最大相同前缀之后的位置
                j = next[j - 1];
            }
            if (str[i] === str[j]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    let next: number[] = getNext(s);
    let sLength: number = s.length;
    let nextLength: number = next.length;
    let suffixLength: number = next[nextLength - 1];
    if (suffixLength > 0 && sLength % (sLength - suffixLength) === 0) return true;
    return false;
};
//leetcode submit region end(Prohibit modification and deletion)
